// Copyright [2022] <Shizhen Zhao>

#ifndef STACK_PULSE_H_
#define STACK_PULSE_H_

#include <functional>
#include <queue>
#include <utility>
#include <vector>
#include <ctime>

#include "algorithm.h"
#include "graph.h"

const int kMaxDelay = 1000;

class StackPulse : public Algorithm {
 public:
    StackPulse() : accurate_(true) {}
    ~StackPulse();
    void SetupTopology(Graph* graph) override;
    Path FindPath(const Flow& flow) override;
    void print() const;

 private:
    template <class T>
    struct Node {
        Node(T id_in, int distance_in)
            : id(id_in), distance(distance_in) {}

        friend bool operator<(const Node<T> &a, const Node<T> &b) {
            return a.distance > b.distance;
        }
        T id;
        int distance;
    };

    struct PulseInfo {
        PulseInfo() : src_delay_to_cost_map(kMaxDelay, kMaxValue) {}
        void Clear() {
            for (int i = 0; i < kMaxDelay; ++i) {
                src_delay_to_cost_map[i] = kMaxValue;
            }
        }
        std::vector<int> src_delay_to_cost_map;
    };

    // Helper functions
    void DstDijkstra(NodeId dst_node, bool flag, int* node_to_dst_dis);
    void Dfs();
    bool updateSrcPath(NodeId u, int cost, int delay);
    void SortLinks();

    // Variables for initialization
    int* dst_cost_map_;
    int* dst_delay_map_;
    int num_nodes_;

    // Variables for pulse search
    clock_t start_time_;
    clock_t end_time_;
    bool* src_visited_;
    PulseInfo* info_;
    Flow flow_;
    int total_cost_;
    Path results_;
    std::vector<std::pair<double, int>> time_ms_cost_pairs_;
    bool accurate_;
};

#endif  // STACK_PULSE_H_